package CH01数组结构.LeetCode栈与队列;

import java.util.LinkedList;

public class LC227 {
    public int calculate(String s) {
        LinkedList<Character> operatorStack = new LinkedList<>();
        LinkedList<Integer> numberStack = new LinkedList<>();

        s = format(s);
        String[] tokens = s.split(" ");
        for (String token : tokens) {
            if (token.length() == 0) {
                continue;
            }
            if (token.equals("+") || token.equals("-")) {
                while (!operatorStack.isEmpty() && (
                        operatorStack.peek() == '+' ||
                                operatorStack.peek() == '-' ||
                                operatorStack.peek() == '*' ||
                                operatorStack.peek() == '/'
                )) {
                    processAnOperator(numberStack,operatorStack);
                }
                operatorStack.push(token.charAt(0));
            } else if (token.equals("*") || token.equals("/")) {
                while (!operatorStack.isEmpty() && (
                        operatorStack.peek() == '*' ||
                                operatorStack.peek() == '/'
                )) {
                    processAnOperator(numberStack,operatorStack);
                }
                operatorStack.push(token.charAt(0));
            } else if (token.equals("(")) {
                operatorStack.push('(');
            } else if (token.equals(")")) {
                while (operatorStack.peek() != '(') {
                    processAnOperator(numberStack,operatorStack);
                }
                operatorStack.pop();
            } else {
                numberStack.push(new Integer(token));
            }
        }
        while (!operatorStack.isEmpty()) {
            processAnOperator(numberStack,operatorStack);
        }
        return numberStack.pop();
    }

    private void processAnOperator(LinkedList<Integer> numberStack, LinkedList<Character> operatorStack) {
        char op = operatorStack.pop();
        int num1 = numberStack.pop();
        int num2 = numberStack.pop();
        if (op == '+') {
            numberStack.push(num2 + num1);
        } else if (op == '-') {
            numberStack.push(num2 - num1);
        } else if (op == '*') {
            numberStack.push(num2 * num1);
        } else {
            numberStack.push(num2 / num1);
        }
    }

    private String format(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}